package red.book._2._1;

public class InsertionSort {

	public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 1; i < N; i++) {
            Comparable temp = a[i];
            int j = i;
            for(; j > 0 && Example.less(temp, a[j - 1]); j--) {
                 a[j] = a[j - 1];
            }
            a[j] = temp;
        }
   }

	public static void main(String[] args) {
		Comparable[] arr = { 5, 3, 1, 4, 2 };
		InsertionSort.sort(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
}
